//
// Description: 工具
// Created by Loading on 2021/12/5.
//

#ifndef PROBLEMS_UTILS_H
#define PROBLEMS_UTILS_H

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

// 根据数组生成链表
ListNode *generateListNode(const vector<int>& nums) {
    if (nums.empty()) {
        return nullptr;
    }
    // 头结点
    auto head = new ListNode(0);
    auto node = head;
    for (auto &x : nums) {
        node->next = new ListNode(x);
        node = node->next;
    }

    return head->next;
}

// 输出链表
string printfListNode(ListNode *head) {
    string s;
    while (head) {
        s += to_string(head->val) + ",";
        head = head->next;
    }
    s.pop_back();
    return s;
}

// 根据数组生成二叉树
TreeNode *generateTreeNode(const vector<int> &nums) {
    if (nums.empty()) {
        return nullptr;
    }

    int n = nums.size();
    function<TreeNode *(int)> innerGenerateTreeNode = [&](int index) -> TreeNode * {
        // -1 为空节点
        if (nums[index] == -1) {
            return nullptr;
        }
        auto root = new TreeNode(nums[index]);
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        if (left < n) {
            root->left = innerGenerateTreeNode(left);
        }
        if (right < n) {
            root->right = innerGenerateTreeNode(right);
        }

        return root;
    };

    TreeNode *root = innerGenerateTreeNode(0);
    return root;
}

// 层序输出二叉树，空节点为null
string printfTreeNodeOfLevel(TreeNode *root) {
    queue<TreeNode *> q;
    // 记录每个节点至前一个节点之间的空节点数量
    unordered_map<TreeNode *, int> m;
    // 当前空节点数量
    int cnt_current_null = 0;

    if (!root) {
        return "null";
    } else {
        q.emplace(root);
    }

    string res;
    while (!q.empty()) {
        //每一层的节点数量
        int size = q.size();

        while (size-- > 0) {
            TreeNode *treeNode = q.front();
            if (m.find(treeNode) != m.end()) {
                // 先输出此节点之前的空节点
                while (m[treeNode]--) {
                    res += "null,";
                }
                m.erase(treeNode);
            }
            res += to_string(treeNode->val) + ",";
            //下一层节点入队列
            if (treeNode->left) {
                q.emplace(treeNode->left);
                if (cnt_current_null > 0) {
                    m[treeNode->left] = cnt_current_null;
                    cnt_current_null = 0;
                }
            } else {
                ++cnt_current_null;
            }
            if (treeNode->right) {
                q.emplace(treeNode->right);
                if (cnt_current_null > 0) {
                    m[treeNode->right] = cnt_current_null;
                    cnt_current_null = 0;
                }
            } else {
                ++cnt_current_null;
            }
            //本层节点出队列
            q.pop();
        }
    }

    res.pop_back();
    return res;
}

#endif //PROBLEMS_UTILS_H
